package com.demo.java.OD201_250.OD241;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【二叉树层次遍历】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145960217
 */
public class OdMain {
    // 递归构建二叉树的方法
    private static Node createTree(char[] post, int start1, int end1, char[] in, int start2,
                                   int end2, Map<Character, Integer> map) {
        // 递归出口：如果范围不合法，返回空树
        if (start1 > end1 || start2 > end2) {
            return null;
        }

        // 根节点是后序遍历数组的最后一个元素
        Node root = new Node(post[end1]);
        // 查找根节点在中序遍历中的位置
        int rootIndex = map.get(root.data);

        // 递归构建左子树和右子树
        root.left = createTree(post, start1, start1 + rootIndex - start2 - 1, in, start2, rootIndex - 1, map);
        root.right = createTree(post, start1 + rootIndex - start2, end1 - 1, in, rootIndex + 1, end2, map);

        return root;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        // 输入后序遍历和中序遍历
        char[] post = s.next().toCharArray();
        char[] in = s.next().toCharArray();

        // 用Map存储中序遍历中每个节点的索引位置，方便快速查找
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }

        // 使用递归方法构建二叉树
        Node root = createTree(post, 0, post.length - 1, in, 0, in.length - 1, map);

        // 构建完成后，进行广度优先遍历（层序遍历）
        StringBuilder builder = new StringBuilder();
        wide(root).forEach(builder::append);
        System.out.println(builder);
    }

    // 广度优先遍历二叉树，返回结果列表
    public static ArrayList<Character> wide(Node root) {
        ArrayList<Character> list = new ArrayList<>();
        if (root == null) return list;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            // 如果当前节点有左子节点，加入队列
            if (node.left != null) queue.offer(node.left);
            // 如果当前节点有右子节点，加入队列
            if (node.right != null) queue.offer(node.right);
            // 将当前节点数据添加到结果列表
            list.add(node.data);
        }
        return list;
    }

    // 定义二叉树的节点结构
    private static class Node {
        char data;
        Node left;
        Node right;

        public Node(char data) {
            this.data = data;
        }
    }
}